package com.fengdi.everyday.middle;

import java.util.*;

public class MaxDistinctElements {
    // 超时了
//    private int res = 1;
//
//    public int maxDistinctElements(int[] nums, int k) {
//        ArrayList<Integer> list = new ArrayList<>();
//        Arrays.stream(nums).forEach(list::add);
//        this.dfs(list, 0, k);
//        return res;
//    }
//
//    void dfs(List<Integer> list, int index, int k) {
//        if(index >= list.size()) {
//            System.out.println(this.res);
//            this.res = Math.max(this.counter(list), this.res);
//            return;
//        }
//
//        int min = -k;
//        int max= k;
//
//        for(int i = -k; i <= k; i++) {
//            int old = list.get(index);
//            list.set(index, old + i);
//            this.dfs(list, index + 1, k);
//            // 还原该位的数字
//            list.set(index, old);
//        }
//    }
//
//    private int counter(List<Integer> list) {
//        // 检测当前数组存在多少不同的数字
//        HashSet<Integer> set = new HashSet<>(list);
//        return set.size();
//    }

    public int maxDistinctElements(int[] nums, int k) {
        Arrays.sort(nums);
        int res = 1;
        nums[0] -= k;
        for(int i = 1, top; i < nums.length; i++) {
            top = nums[i] + k; //当前位置元素所能到达的上界
            if(nums[i] - k > nums[i - 1]) { // 说明num[i]可能变化得到的数字肯定与num[i-1]不同
                res++;
                nums[i] -= k;
            }else if(nums[i - 1] + 1 <= top) { // 前一个元素在范围内
                nums[i] = nums[i - 1] + 1;
                res++;
            }else {
                nums[i] = top;
            }
        }
        return res;
    }
}
